package com.dycong.common.leetcode;

import java.util.Arrays;
import java.util.Random;

/**
 * 给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
 * <p>
 * 例如:
 * <p>
 * 输入:
 * [1,2,3]
 * <p>
 * 输出:
 * 2
 * <p>
 * 说明：
 * 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
 * <p>
 * [1,2,3]  =>  [2,2,3]  =>  [2,2,2]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author dycong
 * @date 2019/11/18 15:10
 */
public class MinMoves2_462 {

    Random random = new Random();

    public static void main(String[] args) {
        MinMoves2_462 minMoves2_462 = new MinMoves2_462();
        int[] nums = {1, 2, 3};
        System.out.println(minMoves2_462.minMoves2(nums));
    }


    public int minMoves2(int[] nums) {
        int ret = 0;
        int medium = quickselect(nums, 0, nums.length-1, nums.length / 2);
        for (int num : nums) {
            ret += Math.abs(num - medium);
        }
        return ret;
    }

    /**
     * 简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。
     *
     * @param nums
     * @param left
     * @param right
     * @param k_smallest
     * @return
     */
    public int quickselect(int[] nums, int left, int right, int k_smallest) {
        if (left == right) // If the list contains only one element,
            return nums[left];  // return that element
        int pivot_index = left + random.nextInt(right - left);

        pivot_index = partition(nums, left, right, pivot_index);

        if (pivot_index == k_smallest) {
            return nums[pivot_index];
        }
        if (k_smallest < pivot_index) {
            //pivot_index - 1
            return quickselect(nums, left, pivot_index - 1, k_smallest);
        }
        //pivot_index + 1
        return quickselect(nums, pivot_index + 1, right, k_smallest);
    }

    public int partition(int[] nums, int left, int right, int pivot_index) {
        // 1. move pivot to end
        swap(nums, pivot_index, right);
        int store_index = left;
        // 2. move all smaller elements to the left
        for (int i = left; i < right; i++) {
            if (nums[i] < nums[right]) {
                if (store_index != i) {
                    swap(nums, store_index, i);
                }
                store_index++;
            }
        }

        // 3. move pivot to its final place
        swap(nums, store_index, right);
        return store_index;
    }


    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public int minMoves2_2(int[] nums) {
        Arrays.sort(nums);
        int ret = 0;
        int medium = nums[nums.length / 2];

        for (int num : nums) {
            ret += Math.abs(medium - num);
        }
        return ret;
    }

}
